package class11;

import java.util.Stack;

/**
 *
 * 暴力递归(就是尝试)
 * 1.把问题转化为规模缩小了的同类问题的子问题(分治)
 * 2.有明确的不需要继续进行递归的条件(base case)
 * 3.有当得到了子问题的结果之后的决策过程(回溯)
 * 4.不记录每一个子问题的解
 *
 *
 * 熟悉尝试:
 * 1.打印n层汉诺塔从最左边移动到最右边的全部过程
 * 汉诺塔(等边三角形的三个顶点各树立一根杆子, 每根杆子上挂载的圆盘只能小圆盘在上,大圆盘在下, 不能出现小压大情形)
 * 左o  右o
 *   中o
 *
 * 假设左边有1 2 3(按数值大小)放置在左边杆上, 需要移动至最右边
 * 那么:
 * 把1移动至右,把2移动至中
 * 把1移动至中,把3移动至右
 * 把1移动至左,把2移动至3
 * 把1移动至3
 *
 * 同理: 移动N层
 * 1-(N-1)层从from至other
 * N层从from至to
 * 1-(N-1)层从other至to(重复前两步逻辑)
 *
 * 最优步数是: 2^N - 1 次
 *
 *
 *
 *
 * 2.打印一个字符串的全部子序列
 * 3.打印一个字符串的全部子序列,要求不要出现重复字面值的子序列
 * 4.打印一个字符串的全部排列
 * 5.打印一个字符串的全部排列,要求不要出现重复的排列
 *
 */
public class Code01_Hanoi {

	public static void hanoi1(int n) {
		//共有左中右组合的 6种组合情况
		//只要样本够大,那么子问题一定会包含所有6种情况
		//左->中
		//左->右
		//中->右
		//中->左
		//右->左
		//右->中
		//不能大压小,那么每次成功将最下一层移动到目标杠,这层处理就完成了
		leftToRight(n);
	}

	// 请把1~N层圆盘 从左 -> 右
	public static void leftToRight(int n) {
		//只剩下第一层,直接移动即可
		if (n == 1) {
			System.out.println("Move 1 from left to right");
			return;
		}
		//1-N层从左至右, 被拆解为:
		//1-(N-1)层从左至中
		leftToMid(n - 1);
		System.out.println("Move " + n + " from left to right");
		//1-(N-1)层从中至右(重复前两步逻辑)
		midToRight(n - 1);
	}

	// 请把1~N层圆盘 从左 -> 中
	public static void leftToMid(int n) {
		if (n == 1) {
			System.out.println("Move 1 from left to mid");
			return;
		}
		//1-N层从左至中, 被拆解为:
		//1-(N-1)层从左至右
		leftToRight(n - 1);
		//N层从左至中
		System.out.println("Move " + n + " from left to mid");
		//1-(N-1)层从右至中
		rightToMid(n - 1);
	}

	public static void rightToMid(int n) {
		if (n == 1) {
			System.out.println("Move 1 from right to mid");
			return;
		}
		rightToLeft(n - 1);
		System.out.println("Move " + n + " from right to mid");
		leftToMid(n - 1);
	}

	public static void midToRight(int n) {
		if (n == 1) {
			System.out.println("Move 1 from mid to right");
			return;
		}
		midToLeft(n - 1);
		System.out.println("Move " + n + " from mid to right");
		leftToRight(n - 1);
	}

	public static void midToLeft(int n) {
		if (n == 1) {
			System.out.println("Move 1 from mid to left");
			return;
		}
		midToRight(n - 1);
		System.out.println("Move " + n + " from mid to left");
		rightToLeft(n - 1);
	}

	public static void rightToLeft(int n) {
		if (n == 1) {
			System.out.println("Move 1 from right to left");
			return;
		}
		rightToMid(n - 1);
		System.out.println("Move " + n + " from right to left");
		midToLeft(n - 1);
	}

	public static void hanoi2(int n) {
		//共有左中右组合的 6种组合情况
		//那么将 左中右具体的方向 转换为 from to other 三种相对抽象的概念
		if (n > 0) {
			func(n, "left", "right", "mid");
		}
	}

	// 1~i 圆盘 目标是from -> to， other是另外一个
	public static void func(int N, String from, String to, String other) {
		if (N == 1) { // base
			System.out.println("Move 1 from " + from + " to " + to);
		} else {
			//主过程的 to -> 子过程的 other, 主过程的 other -> 子过程的 to
			func(N - 1, from, other, to);
			System.out.println("Move " + N + " from " + from + " to " + to);
			//主过程的 from -> 子过程的 other, 主过程的 other -> 子过程的 from
			func(N - 1, other, to, from);
		}
	}

	public static class Record {
		//第一步是否完成
		public boolean finish1;
		public int base;
		public String from;
		public String to;
		public String other;

		public Record(boolean f1, int b, String f, String t, String o) {
			finish1 = false;
			base = b;
			from = f;
			to = t;
			other = o;
		}
	}

	//非递归实现
	//自行模拟压栈
	public static void hanoi3(int N) {
		if (N < 1) {
			return;
		}
		Stack<Record> stack = new Stack<>();
		stack.add(new Record(false, N, "left", "right", "mid"));
		while (!stack.isEmpty()) {
			Record cur = stack.pop();
			//是否是第一层圆盘(最小的圆盘)
			if (cur.base == 1) {
				System.out.println("Move 1 from " + cur.from + " to " + cur.to);
				if (!stack.isEmpty()) {
					//传递这一组的圆盘移动操作是否可以执行的标识, 从最小圆盘完成操作开始标记
					stack.peek().finish1 = true;
				}
			} else {
				if (!cur.finish1) {
					stack.push(cur);
					stack.push(new Record(false, cur.base - 1, cur.from, cur.other, cur.to));
				} else {
					System.out.println("Move " + cur.base + " from " + cur.from + " to " + cur.to);
					stack.push(new Record(false, cur.base - 1, cur.other, cur.to, cur.from));
				}
			}
		}
	}


	public static void main(String[] args) {
		int n = 3;
		hanoi1(n);
		System.out.println("============");
		hanoi2(n);
		System.out.println("============");
		hanoi3(n);
	}

}
